package priv.pront.code.national.acwing.graph;

import java.util.Arrays;
import java.util.Scanner;
/*bellman_ford*/
public class A853_有边数限制的最短路 {

    static int n, m, k;
    static Edge[] edges;
    static int [] dis ,backup;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); m = scanner.nextInt(); k = scanner.nextInt();
        edges = new Edge[m];
        dis = new int[m + 10];
        backup = new int[m + 10];
        for(int i = 0; i < m; i++) edges[i] = new Edge(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
        int t = bellman_ford();
        System.out.println(t == -520 ? "impossible" : t);
    }

    private static int bellman_ford(){
        Arrays.fill(dis, 1000000000);
        dis[1] = 0;
        for(int i = 0; i < k; i++){
            backup = Arrays.copyOf(dis, dis.length);
            for(int j = 0; j < m; j++){
                int a = edges[j].a;
                int b = edges[j].b;
                int w = edges[j].w;
                dis[b] = Math.min(dis[b], backup[a] + w);
            }
        }
        return dis[n] > 1000000000 / 2 ? -520 : dis[n];
    }

    public static class Edge{
        public int a;
        public int b;
        public int w;

        public Edge(int a, int b, int w){
            this.a = a; this.b = b; this.w = w;
        }
    }
}
